const Graph = require("../template")

function testGraphTraversal() {
  console.log(
    "1. 深度优先搜索(DFS)测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D', 'E']
      const edges = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'E']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const visited = []
      graph.dfs('A', (vertex) => visited.push(vertex))
      
      return visited.length === 5 &&
             visited.includes('A') &&
             visited.includes('B') &&
             visited.includes('C') &&
             visited.includes('D') &&
             visited.includes('E')
    })()
  )

  console.log(
    "2. 广度优先搜索(BFS)测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D', 'E']
      const edges = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'E']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const visited = []
      graph.bfs('A', (vertex) => visited.push(vertex))
      
      return visited.length === 5 &&
             visited[0] === 'A' && // BFS从起始点开始
             visited.includes('B') &&
             visited.includes('C') &&
             visited.includes('D') &&
             visited.includes('E')
    })()
  )

  console.log(
    "3. DFS遍历顺序测试:",
    (() => {
      const graph = new Graph()
      
      // 构建简单图
      const vertices = ['A', 'B', 'C']
      const edges = [['A', 'B'], ['B', 'C']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const visited = []
      graph.dfs('A', (vertex) => visited.push(vertex))
      
      return visited.length === 3 &&
             visited[0] === 'A' &&
             visited.includes('B') &&
             visited.includes('C')
    })()
  )

  console.log(
    "4. BFS遍历顺序测试:",
    (() => {
      const graph = new Graph()
      
      // 构建简单图
      const vertices = ['A', 'B', 'C']
      const edges = [['A', 'B'], ['B', 'C']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const visited = []
      graph.bfs('A', (vertex) => visited.push(vertex))
      
      return visited.length === 3 &&
             visited[0] === 'A' &&
             visited.includes('B') &&
             visited.includes('C')
    })()
  )

  console.log(
    "5. 遍历空图测试:",
    (() => {
      const graph = new Graph()
      
      const visited = []
      graph.dfs('A', (vertex) => visited.push(vertex))
      
      return visited.length === 0
    })()
  )

  console.log(
    "6. 遍历单顶点图测试:",
    (() => {
      const graph = new Graph()
      
      graph.addVertex('A')
      
      const visited = []
      graph.dfs('A', (vertex) => visited.push(vertex))
      
      return visited.length === 1 &&
             visited[0] === 'A'
    })()
  )

  console.log(
    "7. 遍历不存在的起始顶点测试:",
    (() => {
      const graph = new Graph()
      
      graph.addVertex('A')
      graph.addVertex('B')
      graph.addEdge('A', 'B')
      
      const visited = []
      graph.dfs('C', (vertex) => visited.push(vertex)) // C不存在
      
      return visited.length === 0
    })()
  )

  console.log(
    "8. 遍历复杂图测试:",
    (() => {
      const graph = new Graph()
      
      // 构建复杂图
      const vertices = ['A', 'B', 'C', 'D', 'E', 'F']
      const edges = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'E'], ['D', 'F'], ['E', 'F']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      const dfsVisited = []
      const bfsVisited = []
      
      graph.dfs('A', (vertex) => dfsVisited.push(vertex))
      graph.bfs('A', (vertex) => bfsVisited.push(vertex))
      
      return dfsVisited.length === 6 &&
             bfsVisited.length === 6 &&
             dfsVisited.includes('A') &&
             bfsVisited.includes('A')
    })()
  )

  console.log(
    "9. this上下文遍历测试:",
    (() => {
      const traversalObj = {
        multiplier: 2,
        processTraversal: function(vertices, edges) {
          const graph = new Graph()
          vertices.forEach(v => graph.addVertex(v))
          edges.forEach(([from, to]) => graph.addEdge(from, to))
          
          let count = 0
          graph.dfs(vertices[0], () => count++)
          return count * this.multiplier
        }
      }
      
      const vertices = ['A', 'B', 'C']
      const edges = [['A', 'B'], ['B', 'C']]
      return traversalObj.processTraversal(vertices, edges) === 6 // 3*2=6
    })()
  )

  console.log(
    "10. 复杂对象this绑定遍历测试:",
    (() => {
      const traversalConfigObj = {
        config: { threshold: 2 },
        processWithConfig: function(vertices, edges) {
          const graph = new Graph()
          vertices.forEach(v => graph.addVertex(v))
          edges.forEach(([from, to]) => graph.addEdge(from, to))
          
          let count = 0
          graph.bfs(vertices[0], () => count++)
          return count >= this.config.threshold
        }
      }
      
      const vertices = ['A', 'B', 'C']
      const edges = [['A', 'B'], ['B', 'C']]
      return traversalConfigObj.processWithConfig(vertices, edges) === true
    })()
  )

  console.log(
    "11. 遍历性能测试:",
    (() => {
      const graph = new Graph()
      
      // 构建大图
      const vertices = Array.from({ length: 100 }, (_, i) => `V${i}`)
      vertices.forEach(v => graph.addVertex(v))
      
      // 添加边
      for (let i = 0; i < 100; i += 2) {
        graph.addEdge(`V${i}`, `V${i + 1}`)
      }
      
      const start = performance.now()
      
      let dfsCount = 0
      let bfsCount = 0
      
      graph.dfs('V0', () => dfsCount++)
      graph.bfs('V0', () => bfsCount++)
      
      const end = performance.now()
      
      return dfsCount > 0 &&
             bfsCount > 0 &&
             (end - start) < 1000 && // 应该在1秒内完成
             (end - start) > 0
    })()
  )

  console.log(
    "12. 遍历一致性测试:",
    (() => {
      const graph = new Graph()
      
      // 构建图
      const vertices = ['A', 'B', 'C', 'D']
      const edges = [['A', 'B'], ['B', 'C'], ['C', 'D']]
      
      vertices.forEach(v => graph.addVertex(v))
      edges.forEach(([from, to]) => graph.addEdge(from, to))
      
      // 多次遍历验证一致性
      let dfsCount1 = 0, dfsCount2 = 0
      let bfsCount1 = 0, bfsCount2 = 0
      
      graph.dfs('A', () => dfsCount1++)
      graph.dfs('A', () => dfsCount2++)
      graph.bfs('A', () => bfsCount1++)
      graph.bfs('A', () => bfsCount2++)
      
      return dfsCount1 === dfsCount2 &&
             bfsCount1 === bfsCount2 &&
             dfsCount1 === 4 &&
             bfsCount1 === 4
    })()
  )
}

testGraphTraversal()
